Automatic authentication systems are employed in applications such as criminal identification, access control systems, and large-scale social service or national identity registry applications. With the emergence of new applications in e-commerce there is a renewed interest in fast and accurate personal identification. For example, in applications such as web-based retailing, autonomous vending, and automated banking, authentication of consumer identity is critical to prevent fraud.
Traditionally, fingerprints have been the most widely used and trusted biometric. The ease of acquisition of fingerprints, the availability of inexpensive fingerprint sensors and a long history of usage in personal identification make fingerprints the most accepted form of authentication at present.
Speed and accuracy are important for biometric authentication systems that operate in realtime applications requiring “on the spot” authentication of users. As noted, fingerprint verification is the biometric authentication method of choice. However, existing fingerprint verification methods necessarily compromise speed for accuracy or vice versa.
The process of fingerprint verification involves two phases: (1) enrolment and (2) matching. A database of the identities of users is maintained. The identity of a person consists of their fingerprint(s) together with other associated data relevant to the particular application (for example, name, age, sex, etc). In the enrolment phase, a person's identity is stored in the database. In the matching phase, the identity claimed by the claimant is verified against the identity stored in the database. If there is a match of the two identities the authentication system declares that the claimant is who they claim to be. The fingerprint stored in the database is the enrollee fingerprint and the fingerprint supplied by the claimant is the claimant fingerprint.
A fingerprint is characterized by smoothly flowing ridges and valleys. The ridge anomalies such as ridge endings and ridge bifurcations are known as “minutiae”. Minutiae are used to determine whether two fingerprints are from the same finger. A feature-extractor provides suitable minutiae information.
The patterns formed by the alternating ridges and valleys are verified as unique to each person over a large population and have been used for personal verification over the past few centuries, primarily in forensic fields.
For automated fingerprint verification, a compact representation of the rich topology of valleys and ridges is desirable. Most automated fingerprint verification systems extract features from the fingerprint images and use the feature sets for verification. There are two basic types of ridge anomalies—ridge termination and ridge bifurcation. The number of minutiae in a fingerprint varies from print to print and typically a feature extractor reports 30 to 60 minutiae per print. In addition to the geometric location of each minutiae on the print, the following structural information is also reported:                1. The angle that the ridge makes at each minutiae with respect to the x-axis        2. The count of ridges between every pair of minutiae.        
Fingerprint verification or one-to-one matching is the problem of confirming or denying a person's claimed identity by comparing a claimant fingerprint against an enrollee fingerprint.
There are various limitations associated with conventional methods of fingerprint verification.                1. The claimant fingerprint is seldom an exact copy of the enrollee fingerprint since there are three degrees of freedom. The three degrees of freedom are (a) translation along the x-axis, (b) translation along the y-axis, and (c) rotation.        2. Most fingerprints are affected to a greater or lesser extent by small to moderate amounts of elastic deformations. Elastic distortions destroy the distance relationships between some minutiae. Such deformations are non-linear (predominantly local) and occur because of pressure and torque variations during fingerprint acquisition.        3. Apart from sensory uncertainty, delocalization of minutiae as a result of feature extraction process is to be taken into account. A ridge is typically 3–5 pixels wide and ridge endings (and similarly, ridge bifurcations) are not represented by a single pixel but are spread over several pixels. Consequently, a feature extractor can pinpoint a minutia to an accuracy of 3–5 pixels.        4. The portion of the fingerprint captured in each image varies with the image. Therefore, the area common to two fingerprints may be small.        5. Most feature extractors report spurious minutiae and do not report some genuine minutiae. This issue is particular problematic especially when the images are of relatively poor quality.        
Major approaches to verification algorithms include modelling the verification problem as:
1. a syntactic pattern recognition problem.
2. a graph matching problem.
3. a global geometric transformation problem.
4. an adaptive elastic string matching problem
It is found, though, that none of these approaches necessarily address the universal problem of simultaneously achieving speed and accuracy suitable for realtime, security applications. In view of the above, it is clearly desirable to provide a method suitable for fingerprint verification which can be performed relatively quickly compared with existing methods, and which provides robust accuracy despite false minutiae, sensor uncertainty, and elastic deformation.